A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances
Luh Yen
Marco Saerens
Amin Mantrach
Masashi Shimbo
This work introduces a new family of link-based dissimilarity measures between nodes of a weighted directed graph. This measure, called the randomized shortest-path (RSP) dissimilarity, depends on a parameter <i>&#952;</i> and has the interesting property of reducing, on one end, to the standard shortest-path distance when <i>&#952;</i> is large and, on the other end, to the commute-time (or resistance) distance when <i>&#952;</i> is small (near zero). Intuitively, it corresponds to the expected cost incurred by a random walker in order to reach a destination node from a starting node while maintaining a constant entropy (related to <i>&#952;</i>) spread in the graph. The parameter <i>&#952;</i> is therefore biasing gradually the simple random walk on the graph towards the shortest-path policy. By adopting a statistical physics approach and computing a sum over all the possible paths (discrete path integral), it is shown that the RSP dissimilarity from every node to a particular node of interest can be computed efficiently by solving two linear systems of <i>n</i> equations, where <i>n</i> is the number of nodes. On the other hand, the dissimilarity between every couple of nodes is obtained by inverting an <i>n</i> x <i>n</i> matrix. The proposed measure can be used for various graph mining tasks such as computing betweenness centrality, finding dense communities, etc, as shown in the experimental section.
